One of the most important requirements for today's high-performance forwarding engines of Internet routers is the ability to identify the packets that belong to a certain flow (a flow is defined by some rule; a collection of rules is called a policy database or a classifier) and apply the actions necessary to satisfy an increasing set of service requirements. Identification of the flow of an incoming packet is termed packet filtering or packet classification.
Packet classification is a key technology for modern high performance routers, as it can be used to provide expedited forwarding of certain type of packets, to enforce security restrictions, or to trigger traffic monitoring. The traditional application of packet filters has been for providing firewall and security functions, such as dropping of unauthorized packets, redirection of packets to proxy servers, etc. The growing complexity of the Internet is creating new applications for packet classification, placing additional demands on the packet classification system of routers and other packet handling devices. An emerging application of packet filters is the identification and classification of packets originated by specific sites, customers, or applications. These actions are related to queueing, scheduling, and routing decisions using not only destination addresses but also source addresses, source port numbers, destination port numbers, etc. Large scale packet filtering functionality enables both edge and core routers to support flexible, customer-specific differentiated services that provide the resources necessary for meeting the services requirements subscribed for.
Packet filters should parse a large portion of the packet header, including information concerning the transport protocol, before forwarding decisions are made. In general, packet classification is performed according to a set of given patterns (rules) that are matched against specified fields in the header of the incoming packet. The router is designed to find the best matching rule among the set of rules that match an incoming packet. The rules are defined either by network management software or by real-time reservation protocols such as RSVP.
It is desirable to use rules that apply to ranges of addresses, port numbers, or protocols, and the rules should not be restricted to exact matches. This allows rules to apply to aggregates and keeps the number of rules to be specified manageable. If filter algorithms can only handle exact matches, then preprocessing must translate ranges in filter rules to exact values. This is infeasible since the size of the ranges grows exponentially with the length of the packet field on which the ranges are defined. As well, the rules must be assigned explicit priorities in order to resolve conflicts if rules overlap.
Many algorithms have been proposed to accomplish packet classification. However, these algorithms are computationally complex, requiring a large amount of space to store the rules, or a large number of memory accesses for an algorithm to perform the classification, or both. When a large number of rules are required for packet classification, all of the previously proposed algorithms become prohibitively expensive to implement for high speed, line rate, real time applications.
One popular hardware device for performing packet classification is a ternary content-addressable memory (TCAM). A TCAM is configured to search the header of the incoming packet against all entries in the forwarding table of the classified database in parallel. It keeps the entries in decreasing order of priority of the rules in a classifier or prefix length of the entries in a forwarding table. Keeping the list sorted under addition and deletion of rules in a classifier is an expensive operation as it takes a large number of memory shifts (write) operations in the worst case. The most common solutions used today for this problem only improve the response for the average case, but waste precious TCAM space, and may still not address a worst case scenario. It is known to use algorithms to manage the TCAM such that incremental update times remain small in the worst case. The principal drawbacks of these algorithms are high power consumption and inefficient representation of filters with port ranges.
Another solution used currently is to use bloom filters as classification filters. A bloom filter is an algorithm that allows one to quickly perform membership tests, the result being a true or false indication for membership. The filter is comprised of a set of k hash functions and a bit vector of a given length. A packet's key that is to be classified is run though the k hash functions. The result of each hash function sets a bit in the bit vector. This bit vector is then compared with a reference bit vector that has been preconfigured with the hash results of the classification database. However, bloom classification filters based are not practical since they are practically incapable of handling rules that are comprised of one or more ranges or wildcard values. To effectively use bloom filters in this scenario, each rule containing wildcards/ranges would need to be explicitly defined and entered into the bloom filter.
To summarize, the algorithms currently used for packet classification are very expensive in terms of space and time complexity. Their use is impractical for high speed, real time classification when a large number of rules exist. As packet rates continue to increase, the need for efficient packet classification methods becomes more and more important. There is a need to provide a means whereby the classification of packets can be accelerated. Furthermore, as deeper packet inspection becomes more prevalent, the processing load of such inspection within the datapath becomes an even greater problem. There is a need to provide a method and a system that significantly reduce the datapath processing load by eliminating packets from being processed by complex classification algorithms.